/*
练习15-2 n皇后问题
分数 25
作者 陈越
单位 浙江大学

在 n×n 的国际象棋棋盘上放 n 个皇后，要求任何两个皇后间不能互相攻击。根据国际象棋规则，皇后可直行、横行、斜行任意多格进行攻击，故问题的要求实际上是：任何两个皇后不能放在同一行、同一列、或同一斜线（斜率为 ±1）上。请设计回溯算法解决 n 皇后问题。
函数接口定义：

void Queens( int n );

函数接口定义中的 n 是棋盘的规模，为 [4, 20] 区间内的整数。

设问题的解表示为状态向量 s

=(s1​,⋯,sn​)，其中 si​=j 表示第 i 行的皇后放在第 j 列上。要求函数 Queens 输出满足要求的解状态 s 中最大的一组，输出时调用裁判给出的函数：

void Print( int *s, int n );

其中 s 是状态向量数组，n 是棋盘的规模。

注意：两组解状态满足 s1​<s2​ 是指，存在下标 0≤k<n 使得 s1​[i]=s2​[i] 对所有 i<k 成立，并且 s1​[k]<s2​[k]。

输入样例：

5

输出样例：

( 5 3 1 4 2 )
*/

#include <stdio.h>

void Print( int *s, int n );
void Queens( int n );

int main(void)
{    
    int n;
    
    scanf("%d", &n);
    Queens(n);
    
    return 0;
}

/* 你的代码将被嵌在这里 */

void Print(int *s, int n) {
    printf("( ");
    for (int i = 0; i < n; i++) {
        printf("%d ", s[i] + 1);
    }
    printf(")\n");
}

int compare(int *s1, int *s2, int n) {
    for (int i = 0; i < n; i++) {
        if (s1[i] < s2[i]) {
            return -1;
        } else if (s1[i] > s2[i]) {
            return 1;
        }
    }
    return 0;
}

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

bool isSafe(int *s, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (s[i] == col || abs(s[i] - col) == abs(i - row)) {
            return false;
        }
    }
    return true;
}

bool solveNQueens(int *s, int row, int n, bool *foundSolution) {
    if (row == n) {
        // Print(s, n);
        *foundSolution = true;
        return true;
    }

    for (int col = n-1; col >= 0; col--) {
        if (isSafe(s, row, col)) {
            s[row] = col;
            if (solveNQueens(s, row + 1, n, foundSolution)) {
                return true;
            }
        }
    }
    return false;
}

void Queens(int n) {
    int *s = (int *)malloc(n * sizeof(int));
    
    bool foundSolution = false;
    solveNQueens(s, 0, n, &foundSolution);

    Print(s, n);

    free(s);
}
